
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

class Solution {
public:
    unordered_map<Node*, Node*> visited;

    Node* cloneGraph(Node* node) {
        if(node==nullptr) return node;
        if(visited.find(node)!=visited.end()) return visited[node]; //已访问

        Node *clone=new Node(node->val);

        visited[node]=clone;

        for(auto &neighbor:node->neighbors) clone->neighbors.emplace_back(cloneGraph(neighbor));

        return clone;

    }
}; 